МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД
«УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»
Інженерно-технічний факультет
Кафедра копм’ютерних систем та мереж
Розрахунково-графічна робота
з дисципліни
«Теоретичні основи цифрової обробки сигналів»
на тему:
«Розрахунок параметрів виконання алгоритму ШПФ»
Завдання
Варіант № 6
Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними:
Кількістьточок
1024
Основа ШПФ
2
Прорідження
частотне
Частота роботи процесора
0,25МГц
Розрядністьвхіднихданих
24(12+12)
Тип вхідного інтерфейсу, пристрою
USB
Тип вихідного інтерфейсу, пристрою
Спец.(20 нс)
Анотація
В даній розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 2 для 24-розрядних вхідних даних з частотним прорідженням, розроблено:
граф алгоритму ШПФ з основою 2;
біт інверсний порядок видачі даних;
блок-схему перетворення;
обчислено часові ресурси для виконання обчислення;
функціональну схему;
програму виконання алгоритму ШПФ.
Зміст
Вступ 5
1. Теоретична частина 6
1.1. Основні визначення 6
1.2. Властивості повертаючих множників 6
1.3. Основні формули 7
2. Практична частина 9
2.1. Побудова графа алгоритму ШПФ з основою 2 9
2.2. Біт інверсний порядок видачі даних 11
2.3. Блок-схема перетворення 12
3. Розрахунковий розділ 13
4 Розробка функціональної схеми 15
5. Розробка програми 16
Висновки 19
Література 20
Вступ
Перетворення Фур'є - це функція, що описує амплітуду та фазу кожної синусоїда, що відповідає певній частоті. Амплітуда представляє висоту кривої, а фаза - початкову точку синусоїда.
Алгоритм швидкого перетворення Фур'є – є оптимізованим за швидкодією способом обчислення дискретного перетворення Фур'є (ДПФ), що має складність O(Nlog2N) на відміну від складності ДПФ порядку O(N2).
Розробка програм алгоритму ШПФ є одним з етапів розробки процесора ШПФ, ефективність якої суттєво впливає на технічні параметри процесора.
Основними сферами застосування ДПФ є:
- цифровий спектральний аналіз - аналізатори спектра, обробка мови, обробка зображень, розпізнавання образів;
- проектування фільтрів - обчислення імпульсної характеристики за частотною та частотної характеристики за імпульсною.
Ці перетворення зворотні, при чому зворотнє перетворення має практично таку ж саму форму, що й пряме перетворення.
Швидке перетворення Фур'є застосовується в багатьох галузях: радіолокации, стисненні відео та зображень, геології. Багато з цих задач вимагають виконання перетворень в реальному часі, з мінімальною часовою затримкою обчислень.
Для зменшення часу, необхідного для виконання перетворень, можливо розпаралелювання задачі, виконання її на паралельній обчислювальній системі.
1. Теоретична частина
1.1. Основні визначення
Визначення 1. Дано кінцеву послідовність x0, x1, x2,..., xN-1 (у загальному випадку комплексних чисел). ДПФ полягає в пошуку послідовності X0, X1, X2,..., XN-1, елементи якої обчислюються за формулою:
/ (1)
Визначення 2. Зворотне ДПФ полягає в пошуку послідовності x0, x1, x2,..., xN-1, елементи якої обчислюються за формулою:
/ (2)
Основною властивістю перетворень (1) і (2) є те, що з послідовності {x} отримується (при прямому перетворенні) послідовність {X}, а якщо застосувати до {X} зворотне перетворення, то знову отримується вихідна послідовність {x}.
Визначення 3. Величина / називається повертаючим множником.
1.2. Властивості повертаючих множників
При k = 1 /
Пряме перетворення Фур’є можна виразити через повертаючі множники. Тоді формула (1) матиме вигляд: / (3)
Геометричне тлумачення повертаючих множників наведене на рис.1. Комплексне число (rejφ) представлене у вигляді вектора, що виходить із початку координат (r - модуль числа, а φ – аргумент). Модуль відповідає довжині вектора, а аргумент - куту ...